home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 2002 #11 / Amiga Plus CD - 2002 - No. 11.iso / Tools / Development / libogg / libogg-1.0rc3 / src / bitwise.c next >
Encoding:
C/C++ Source or Header  |  2002-10-27  |  11.4 KB  |  434 lines
  1. /********************************************************************
  2.  *                                                                  *
  3.  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
  4.  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
  5.  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
  6.  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
  7.  *                                                                  *
  8.  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001             *
  9.  * by the XIPHOPHORUS Company http://www.xiph.org/                  *
  10.  *                                                                  *
  11.  ********************************************************************
  12.  
  13.   function: packing variable sized words into an octet stream
  14.   last mod: $Id: bitwise.c,v 1.10 2001/12/21 14:41:15 segher Exp $
  15.  
  16.  ********************************************************************/
  17.  
  18. /* We're 'LSb' endian; if we write a word but read individual bits,
  19.    then we'll read the lsb first */
  20.  
  21. #include <string.h>
  22. #include <stdlib.h>
  23. #include <ogg/ogg.h>
  24.  
  25. #define BUFFER_INCREMENT 256
  26.  
  27. static unsigned long mask[]=
  28. {0x00000000,0x00000001,0x00000003,0x00000007,0x0000000f,
  29.  0x0000001f,0x0000003f,0x0000007f,0x000000ff,0x000001ff,
  30.  0x000003ff,0x000007ff,0x00000fff,0x00001fff,0x00003fff,
  31.  0x00007fff,0x0000ffff,0x0001ffff,0x0003ffff,0x0007ffff,
  32.  0x000fffff,0x001fffff,0x003fffff,0x007fffff,0x00ffffff,
  33.  0x01ffffff,0x03ffffff,0x07ffffff,0x0fffffff,0x1fffffff,
  34.  0x3fffffff,0x7fffffff,0xffffffff };
  35.  
  36. void oggpack_writeinit(oggpack_buffer *b){
  37.   memset(b,0,sizeof(*b));
  38.   b->ptr=b->buffer=_ogg_malloc(BUFFER_INCREMENT);
  39.   b->buffer[0]='\0';
  40.   b->storage=BUFFER_INCREMENT;
  41. }
  42.  
  43. void oggpack_reset(oggpack_buffer *b){
  44.   b->ptr=b->buffer;
  45.   b->buffer[0]=0;
  46.   b->endbit=b->endbyte=0;
  47. }
  48.  
  49. void oggpack_writeclear(oggpack_buffer *b){
  50.   _ogg_free(b->buffer);
  51.   memset(b,0,sizeof(*b));
  52. }
  53.  
  54. void oggpack_readinit(oggpack_buffer *b,unsigned char *buf,int bytes){
  55.   memset(b,0,sizeof(*b));
  56.   b->buffer=b->ptr=buf;
  57.   b->storage=bytes;
  58. }
  59.  
  60. /* Takes only up to 32 bits. */
  61. void oggpack_write(oggpack_buffer *b,unsigned long value,int bits){
  62.   if(b->endbyte+4>=b->storage){
  63.     b->buffer=_ogg_realloc(b->buffer,b->storage+BUFFER_INCREMENT);
  64.     b->storage+=BUFFER_INCREMENT;
  65.     b->ptr=b->buffer+b->endbyte;
  66.   }
  67.  
  68.   value&=mask[bits]; 
  69.   bits+=b->endbit;
  70.  
  71.   b->ptr[0]|=value<<b->endbit;  
  72.   
  73.   if(bits>=8){
  74.     b->ptr[1]=value>>(8-b->endbit);  
  75.     if(bits>=16){
  76.       b->ptr[2]=value>>(16-b->endbit);  
  77.       if(bits>=24){
  78.     b->ptr[3]=value>>(24-b->endbit);  
  79.     if(bits>=32){
  80.       if(b->endbit)
  81.         b->ptr[4]=value>>(32-b->endbit);
  82.       else
  83.         b->ptr[4]=0;
  84.     }
  85.       }
  86.     }
  87.   }
  88.  
  89.   b->endbyte+=bits/8;
  90.   b->ptr+=bits/8;
  91.   b->endbit=bits&7;
  92. }
  93.  
  94. /* Read in bits without advancing the bitptr; bits <= 32 */
  95. long oggpack_look(oggpack_buffer *b,int bits){
  96.   unsigned long ret;
  97.   unsigned long m=mask[bits];
  98.  
  99.   bits+=b->endbit;
  100.  
  101.   if(b->endbyte+4>=b->storage){
  102.     /* not the main path */
  103.     if(b->endbyte+(bits-1)/8>=b->storage)return(-1);
  104.   }
  105.   
  106.   ret=b->ptr[0]>>b->endbit;
  107.   if(bits>8){
  108.     ret|=b->ptr[1]<<(8-b->endbit);  
  109.     if(bits>16){
  110.       ret|=b->ptr[2]<<(16-b->endbit);  
  111.       if(bits>24){
  112.     ret|=b->ptr[3]<<(24-b->endbit);  
  113.     if(bits>32 && b->endbit)
  114.       ret|=b->ptr[4]<<(32-b->endbit);
  115.       }
  116.     }
  117.   }
  118.   return(m&ret);
  119. }
  120.  
  121. long oggpack_look1(oggpack_buffer *b){
  122.   if(b->endbyte>=b->storage)return(-1);
  123.   return((b->ptr[0]>>b->endbit)&1);
  124. }
  125.  
  126. /* Read in bits without advancing the bitptr; bits <= 8 */
  127. /* we never return 'out of bits'; we'll handle it on _adv */
  128. long oggpack_look_huff(oggpack_buffer *b,int bits){
  129.   unsigned long ret;
  130.   unsigned long m=mask[bits];
  131.   
  132.   bits+=b->endbit;
  133.   
  134.   ret=b->ptr[0]>>b->endbit;
  135.   if(bits>8){
  136.     ret|=b->ptr[1]<<(8-b->endbit);  
  137.   }
  138.   return(m&ret);
  139. }
  140.  
  141. void oggpack_adv(oggpack_buffer *b,int bits){
  142.   bits+=b->endbit;
  143.   b->ptr+=bits/8;
  144.   b->endbyte+=bits/8;
  145.   b->endbit=bits&7;
  146. }
  147.  
  148. void oggpack_adv1(oggpack_buffer *b){
  149.   if(++(b->endbit)>7){
  150.     b->endbit=0;
  151.     b->ptr++;
  152.     b->endbyte++;
  153.   }
  154. }
  155.  
  156. /* have to check for overflow now. return -1 on overflow */
  157. int oggpack_adv_huff(oggpack_buffer *b,int bits){
  158.   if(b->endbyte+(b->endbit+bits-1)/8>=b->storage)return(-1);
  159.   bits+=b->endbit;
  160.   b->ptr+=bits/8;
  161.   b->endbyte+=bits/8;
  162.   b->endbit=bits&7;
  163.   return 0;
  164. }
  165.  
  166. /* bits <= 32 */
  167. long oggpack_read(oggpack_buffer *b,int bits){
  168.   unsigned long ret;
  169.   unsigned long m=mask[bits];
  170.  
  171.   bits+=b->endbit;
  172.  
  173.   if(b->endbyte+4>=b->storage){
  174.     /* not the main path */
  175.     ret=-1UL;
  176.     if(b->endbyte+(bits-1)/8>=b->storage)goto overflow;
  177.   }
  178.   
  179.   ret=b->ptr[0]>>b->endbit;
  180.   if(bits>8){
  181.     ret|=b->ptr[1]<<(8-b->endbit);  
  182.     if(bits>16){
  183.       ret|=b->ptr[2]<<(16-b->endbit);  
  184.       if(bits>24){
  185.     ret|=b->ptr[3]<<(24-b->endbit);  
  186.     if(bits>32 && b->endbit){
  187.       ret|=b->ptr[4]<<(32-b->endbit);
  188.     }
  189.       }
  190.     }
  191.   }
  192.   ret&=m;
  193.   
  194.  overflow:
  195.  
  196.   b->ptr+=bits/8;
  197.   b->endbyte+=bits/8;
  198.   b->endbit=bits&7;
  199.   return(ret);
  200. }
  201.  
  202. long oggpack_read1(oggpack_buffer *b){
  203.   unsigned long ret;
  204.   
  205.   if(b->endbyte>=b->storage){
  206.     /* not the main path */
  207.     ret=-1UL;
  208.     goto overflow;
  209.   }
  210.  
  211.   ret=(b->ptr[0]>>b->endbit)&1;
  212.   
  213.  overflow:
  214.  
  215.   b->endbit++;
  216.   if(b->endbit>7){
  217.     b->endbit=0;
  218.     b->ptr++;
  219.     b->endbyte++;
  220.   }
  221.   return(ret);
  222. }
  223.  
  224. long oggpack_bytes(oggpack_buffer *b){
  225.   return(b->endbyte+(b->endbit+7)/8);
  226. }
  227.  
  228. long oggpack_bits(oggpack_buffer *b){
  229.   return(b->endbyte*8+b->endbit);
  230. }
  231.  
  232. unsigned char *oggpack_get_buffer(oggpack_buffer *b){
  233.   return(b->buffer);
  234. }
  235.  
  236. /* Self test of the bitwise routines; everything else is based on
  237.    them, so they damned well better be solid. */
  238.  
  239. #ifdef _V_SELFTEST
  240. #include <stdio.h>
  241.  
  242. static int ilog(unsigned int v){
  243.   int ret=0;
  244.   while(v){
  245.     ret++;
  246.     v>>=1;
  247.   }
  248.   return(ret);
  249. }
  250.       
  251. oggpack_buffer o;
  252. oggpack_buffer r;
  253.  
  254. void report(char *in){
  255.   fprintf(stderr,"%s",in);
  256.   exit(1);
  257. }
  258.  
  259. void cliptest(unsigned long *b,int vals,int bits,int *comp,int compsize){
  260.   long bytes,i;
  261.   unsigned char *buffer;
  262.  
  263.   oggpack_reset(&o);
  264.   for(i=0;i<vals;i++)
  265.     oggpack_write(&o,b[i],bits?bits:ilog(b[i]));
  266.   buffer=oggpack_get_buffer(&o);
  267.   bytes=oggpack_bytes(&o);
  268.   if(bytes!=compsize)report("wrong number of bytes!\n");
  269.   for(i=0;i<bytes;i++)if(buffer[i]!=comp[i]){
  270.     for(i=0;i<bytes;i++)fprintf(stderr,"%x %x\n",(int)buffer[i],(int)comp[i]);
  271.     report("wrote incorrect value!\n");
  272.   }
  273.   oggpack_readinit(&r,buffer,bytes);
  274.   for(i=0;i<vals;i++){
  275.     int tbit=bits?bits:ilog(b[i]);
  276.     if(oggpack_look(&r,tbit)==-1)
  277.       report("out of data!\n");
  278.     if(oggpack_look(&r,tbit)!=(b[i]&mask[tbit]))
  279.       report("looked at incorrect value!\n");
  280.     if(tbit==1)
  281.       if(oggpack_look1(&r)!=(b[i]&mask[tbit]))
  282.     report("looked at single bit incorrect value!\n");
  283.     if(tbit==1){
  284.       if(oggpack_read1(&r)!=(b[i]&mask[tbit]))
  285.     report("read incorrect single bit value!\n");
  286.     }else{
  287.     if(oggpack_read(&r,tbit)!=(b[i]&mask[tbit]))
  288.       report("read incorrect value!\n");
  289.     }
  290.   }
  291.   if(oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
  292. }
  293.  
  294. int main(void){
  295.   unsigned char *buffer;
  296.   long bytes,i;
  297.   static unsigned long testbuffer1[]=
  298.     {18,12,103948,4325,543,76,432,52,3,65,4,56,32,42,34,21,1,23,32,546,456,7,
  299.        567,56,8,8,55,3,52,342,341,4,265,7,67,86,2199,21,7,1,5,1,4};
  300.   int test1size=43;
  301.  
  302.   static unsigned long testbuffer2[]=
  303.     {216531625L,1237861823,56732452,131,3212421,12325343,34547562,12313212,
  304.        1233432,534,5,346435231,14436467,7869299,76326614,167548585,
  305.        85525151,0,12321,1,349528352};
  306.   int test2size=21;
  307.  
  308.   static unsigned long large[]=
  309.     {2136531625L,2137861823,56732452,131,3212421,12325343,34547562,12313212,
  310.        1233432,534,5,2146435231,14436467,7869299,76326614,167548585,
  311.        85525151,0,12321,1,2146528352};
  312.  
  313.   static unsigned long testbuffer3[]=
  314.     {1,0,14,0,1,0,12,0,1,0,0,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,1,1,1,1,0,0,1,
  315.        0,1,30,1,1,1,0,0,1,0,0,0,12,0,11,0,1,0,0,1};
  316.   int test3size=56;
  317.  
  318.   int onesize=33;
  319.   static int one[]={146,25,44,151,195,15,153,176,233,131,196,65,85,172,47,40,
  320.                     34,242,223,136,35,222,211,86,171,50,225,135,214,75,172,
  321.                     223,4};
  322.  
  323.   int twosize=6;
  324.   static int two[]={61,255,255,251,231,29};
  325.  
  326.   int threesize=54;
  327.   static int three[]={169,2,232,252,91,132,156,36,89,13,123,176,144,32,254,
  328.                       142,224,85,59,121,144,79,124,23,67,90,90,216,79,23,83,
  329.                       58,135,196,61,55,129,183,54,101,100,170,37,127,126,10,
  330.                       100,52,4,14,18,86,77,1};
  331.  
  332.   int foursize=38;
  333.   static int four[]={18,6,163,252,97,194,104,131,32,1,7,82,137,42,129,11,72,
  334.                      132,60,220,112,8,196,109,64,179,86,9,137,195,208,122,169,
  335.                      28,2,133,0,1};
  336.  
  337.   int fivesize=45;
  338.   static int five[]={169,2,126,139,144,172,30,4,80,72,240,59,130,218,73,62,
  339.                      241,24,210,44,4,20,0,248,116,49,135,100,110,130,181,169,
  340.                      84,75,159,2,1,0,132,192,8,0,0,18,22};
  341.  
  342.   int sixsize=7;
  343.   static int six[]={17,177,170,242,169,19,148};
  344.  
  345.   /* Test read/write together */
  346.   /* Later we test against pregenerated bitstreams */
  347.   oggpack_writeinit(&o);
  348.  
  349.   fprintf(stderr,"\nSmall preclipped packing: ");
  350.   cliptest(testbuffer1,test1size,0,one,onesize);
  351.   fprintf(stderr,"ok.");
  352.  
  353.   fprintf(stderr,"\nNull bit call: ");
  354.   cliptest(testbuffer3,test3size,0,two,twosize);
  355.   fprintf(stderr,"ok.");
  356.  
  357.   fprintf(stderr,"\nLarge preclipped packing: ");
  358.   cliptest(testbuffer2,test2size,0,three,threesize);
  359.   fprintf(stderr,"ok.");
  360.  
  361.   fprintf(stderr,"\n32 bit preclipped packing: ");
  362.   oggpack_reset(&o);
  363.   for(i=0;i<test2size;i++)
  364.     oggpack_write(&o,large[i],32);
  365.   buffer=oggpack_get_buffer(&o);
  366.   bytes=oggpack_bytes(&o);
  367.   oggpack_readinit(&r,buffer,bytes);
  368.   for(i=0;i<test2size;i++){
  369.     if(oggpack_look(&r,32)==-1)report("out of data. failed!");
  370.     if(oggpack_look(&r,32)!=large[i]){
  371.       fprintf(stderr,"%ld != %ld (%lx!=%lx):",oggpack_look(&r,32),large[i],
  372.           oggpack_look(&r,32),large[i]);
  373.       report("read incorrect value!\n");
  374.     }
  375.     oggpack_adv(&r,32);
  376.   }
  377.   if(oggpack_bytes(&r)!=bytes)report("leftover bytes after read!\n");
  378.   fprintf(stderr,"ok.");
  379.  
  380.   fprintf(stderr,"\nSmall unclipped packing: ");
  381.   cliptest(testbuffer1,test1size,7,four,foursize);
  382.   fprintf(stderr,"ok.");
  383.  
  384.   fprintf(stderr,"\nLarge unclipped packing: ");
  385.   cliptest(testbuffer2,test2size,17,five,fivesize);
  386.   fprintf(stderr,"ok.");
  387.  
  388.   fprintf(stderr,"\nSingle bit unclipped packing: ");
  389.   cliptest(testbuffer3,test3size,1,six,sixsize);
  390.   fprintf(stderr,"ok.");
  391.  
  392.   fprintf(stderr,"\nTesting read past end: ");
  393.   oggpack_readinit(&r,"\0\0\0\0\0\0\0\0",8);
  394.   for(i=0;i<64;i++){
  395.     if(oggpack_read(&r,1)!=0){
  396.       fprintf(stderr,"failed; got -1 prematurely.\n");
  397.       exit(1);
  398.     }
  399.   }
  400.   if(oggpack_look(&r,1)!=-1 ||
  401.      oggpack_read(&r,1)!=-1){
  402.       fprintf(stderr,"failed; read past end without -1.\n");
  403.       exit(1);
  404.   }
  405.   oggpack_readinit(&r,"\0\0\0\0\0\0\0\0",8);
  406.   if(oggpack_read(&r,30)!=0 || oggpack_read(&r,16)!=0){
  407.       fprintf(stderr,"failed 2; got -1 prematurely.\n");
  408.       exit(1);
  409.   }
  410.  
  411.   if(oggpack_look(&r,18)!=0 ||
  412.      oggpack_look(&r,18)!=0){
  413.     fprintf(stderr,"failed 3; got -1 prematurely.\n");
  414.       exit(1);
  415.   }
  416.   if(oggpack_look(&r,19)!=-1 ||
  417.      oggpack_look(&r,19)!=-1){
  418.     fprintf(stderr,"failed; read past end without -1.\n");
  419.       exit(1);
  420.   }
  421.   if(oggpack_look(&r,32)!=-1 ||
  422.      oggpack_look(&r,32)!=-1){
  423.     fprintf(stderr,"failed; read past end without -1.\n");
  424.       exit(1);
  425.   }
  426.   fprintf(stderr,"ok.\n\n");
  427.  
  428.  
  429.   return(0);
  430. }  
  431. #endif  /* _V_SELFTEST */
  432.  
  433. #undef BUFFER_INCREMENT
  434.